package com.example.demo.suanfa_sort;

import org.junit.Test;

/**
 * 适用二分法找到一个局部最小
 * <p>
 * 给定一组数，任意相邻位置两个数不相等；
 * 找出 是否有局部最小，找出任意一个即可！
 */
public class AwesomeDemo {


    /**
     * 可以适用数轴：
     * 或者变相的理解为：找到数组内的一个低点
     * 趋势下\      /趋势上
     * 低点
     * 方法：
     * 1.判断两端 是否存在低点，有则返回即可
     * 2.因为两端都不存在，顾 0->i \ 一定是向下趋势
     * 3.i-> length-1 位置 一定为 / 向上趋势，
     * 4.顾 在 0->length-1位置一定存在一个最低点
     * <p>
     * 查看每一次mid位置，是否 是 mid-1 和 mid+1 的最低点
     *
     * @param arr
     * @return
     */
    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        int length = arr.length;
        if (arr[length - 1] < arr[length - 2]) {
            return length - 1;
        }

/////////
        int left = 1;
        int right = length - 2;
        int mid = 0;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (arr[mid - 1] < arr[mid]) {
                right = mid - 1;
            } else if (arr[mid + 1] < arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    @Test
    public void test() {
        System.out.println(12 & (-12));
    }


}
